package cn.njupt.tree;
//红黑树
public class RBTree<E> extends BBST<E> {
    public static final boolean RED=true;
    public static final boolean BLACK=false;
    public RBTree(){
        this(null);
    }
    public RBTree(Comparator<E> comparator) {
        super(comparator);
    }

    @Override
    public void afterAdd(Node<E> child) {
        Node<E> parent=child.parent;
        if(parent==null){
            colorBlack(child);
            return;
        }
        if(isBlack(parent))return;
        Node<E> grand=parent.parent;
        Node<E> uncle=parent.brother();

        if(isRed(uncle)){
            //叔父节点是红色
            colorBlack(parent);
            colorBlack(uncle);
            colorRed(parent.parent);
            afterAdd(parent.parent);
            return;
        }
        //叔父节点不是红色，就要分情况进行LL,LR,RR,RL
        if(parent.isLeftChild()){
            //L
            if(child.isLeftChild()){
//                LL
                colorBlack(parent);
                colorRed(grand);
                rotateRight(grand);
            }else{
                //LR
                colorBlack(child);
                colorRed(grand);
                rotateLeft(parent);
                rotateRight(grand);
            }
        }else{
            if(child.isRightChild()){
//                RR
                colorRed(grand);
                colorBlack(parent);
                rotateLeft(grand);
            }else{
//                RL
                colorBlack(child);
                colorRed(grand);
                rotateRight(parent);
                rotateLeft(grand);
            }
        }
    }

    @Override
    public void afterRemove(Node<E> node) {


        //下面删除的黑色节点，并且黑色节点不是叶子节点
        if(isRed(node)){
            colorBlack(node);
            return;
        }

        Node<E> parent=node.parent;
        if(parent==null){
            return;
        }

        //下面删除的是黑色叶子节点
        boolean left=parent.left==null || node.isLeftChild();
        if(left){
            //被删除的节点相当于父节点的左边
            Node<E> brother=parent.right;
            if(isRed(brother)){
                colorBlack(brother);
                colorRed(parent);
                rotateLeft(parent);
                brother=parent.right;
            }
            if(isBlack(brother.left) &&  isBlack(brother.right)){
                //兄弟节点是一个黑色节点，并且黑色节点没有红色子节点
                boolean parentBlack=isBlack(parent);
                colorRed(brother);
                colorBlack(parent);
                if(parentBlack){
                    afterRemove(parent);
                }

            }else{
                //兄弟节点是一个黑色节点，并且黑色节点有红色子节点
                if(isBlack(brother.right)){
                    rotateRight(brother);
                    brother=parent.right;
                }
                color(brother,colorOf(parent));
                colorBlack(parent);
                colorBlack(brother.right);
                rotateLeft(parent);
            }
        }else{
            //被删除的节点相当于父节点的右边
            Node<E> brother=parent.left;
            if(isRed(brother)){
                colorBlack(brother);
                colorRed(parent);
                rotateRight(parent);
                brother=parent.left;
            }
            if(isBlack(brother.left) &&  isBlack(brother.right)){
                //兄弟节点是一个黑色节点，并且黑色节点没有红色子节点
                boolean parentBlack=isBlack(parent);
                colorRed(brother);
                colorBlack(parent);
                if(parentBlack){
                    afterRemove(parent);
                }

            }else{
                //兄弟节点是一个黑色节点，并且黑色节点有红色子节点
                if(isBlack(brother.left)){
                    rotateLeft(brother);
                    brother=parent.left;
                }
                color(brother,colorOf(parent));
                colorBlack(parent);
                colorBlack(brother.left);
                rotateRight(parent);
            }
        }
    }


    public void afterRemove2(Node<E> node,Node<E> replacement) {
        //删除的是红色节点
        if(isRed(node)){
            return;
        }

        //下面删除的黑色节点，并且黑色节点不是叶子节点
        if(isRed(replacement)){
            colorBlack(replacement);
            return;
        }

        Node<E> parent=node.parent;
        if(parent==null){
            return;
        }

        //下面删除的是黑色叶子节点
        boolean left=parent.left==null || node.isLeftChild();
        if(left){
            //被删除的节点相当于父节点的左边
            Node<E> brother=parent.right;
            if(isRed(brother)){
                colorBlack(brother);
                colorRed(parent);
                rotateLeft(parent);
                brother=parent.right;
            }
            if(isBlack(brother.left) &&  isBlack(brother.right)){
                //兄弟节点是一个黑色节点，并且黑色节点没有红色子节点
                boolean parentBlack=isBlack(parent);
                colorRed(brother);
                colorBlack(parent);
                if(parentBlack){
                    afterRemove(parent);
                }

            }else{
                //兄弟节点是一个黑色节点，并且黑色节点有红色子节点
                if(isBlack(brother.right)){
                    rotateRight(brother);
                    brother=parent.right;
                }
                color(brother,colorOf(parent));
                colorBlack(parent);
                colorBlack(brother.right);
                rotateLeft(parent);
            }
        }else{
            //被删除的节点相当于父节点的右边
            Node<E> brother=parent.left;
            if(isRed(brother)){
                colorBlack(brother);
                colorRed(parent);
                rotateRight(parent);
                brother=parent.left;
            }
            if(isBlack(brother.left) &&  isBlack(brother.right)){
                //兄弟节点是一个黑色节点，并且黑色节点没有红色子节点
                boolean parentBlack=isBlack(parent);
                colorRed(brother);
                colorBlack(parent);
                if(parentBlack){
                    afterRemove(parent);
                }

            }else{
                //兄弟节点是一个黑色节点，并且黑色节点有红色子节点
                if(isBlack(brother.left)){
                    rotateLeft(brother);
                    brother=parent.left;
                }
                color(brother,colorOf(parent));
                colorBlack(parent);
                colorBlack(brother.left);
                rotateRight(parent);
            }
        }
    }



    //继承BBST即可
    /*public void rotateLeft(Node<E> grand){
        //向左旋转
        Node<E> parent=grand.right;
        Node<E> parentLeft=parent.left;

        grand.right=parentLeft;

        if(parentLeft!=null){
            parentLeft.parent=grand;
        }

        parent.left=grand;
        parent.parent=grand.parent;
        if(grand.parent==null){
            root=parent;
        }else if(grand.isLeftChild()){
            grand.parent.left=parent;
        }else{
            grand.parent.right=parent;
        }
        grand.parent=parent;
    }*/

    /*public void rotateRight(Node<E> grand){
        //向右旋转
        //向左旋转
        Node<E> parent=grand.left;
        Node<E> parentRight=parent.right;

        grand.left=parentRight;

        if(parentRight!=null){
            parentRight.parent=grand;
        }

        parent.right=grand;
        parent.parent=grand.parent;
        if(grand.parent==null){
            root=parent;
        }else if(grand.isLeftChild()){
            grand.parent.left=parent;
        }else{
            grand.parent.right=parent;
        }
        grand.parent=parent;
    }*/

    @Override
    public Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<E>(element, parent);
    }




    //判断是否是红色节点
    public boolean isRed(Node<E> node){
        return node==null?false:((RBNode)node).color==RED;
    }
    //判断是否是黑色节点
    public boolean isBlack(Node<E> node){
        return node==null?true:((RBNode)node).color==BLACK;
    }
    public Node<E> color(Node<E> node,boolean color){
        if(node==null)return node;
        ((RBNode<E>)node).color=color;
        return node;
    }

    public boolean colorOf(Node<E> node){
        return node==null?BLACK:((RBNode)node).color;
    }

    //染成红色
    public void colorRed(Node<E> node){
        color(node,RED);
    }
    //染成黑色
    public void colorBlack(Node<E> node){
        color(node,BLACK);
    }


    private static class RBNode<E> extends Node<E>{
        boolean color=RED;
        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }

        @Override
        public String toString() {
            return element+"_"+(this.color==BLACK?"black":"red");
        }
    }
}
